


Once the \emph{parse graph} is created for a particular user's question, 
the system has to ensure domain- and aplication-specific constraints.
%that we discuss in this section.
%, before an actual structured 
%query can be generated (see next section).  
%
%For our BI use-case, some constraints have been mentioned in
%section~\ref{sec:problem}.
In addition to constraints mentioned in section~\ref{sec:problem} for our BI
use-case, other
%The most obvious ones were to ensure that recognized entities
%belong to one data warehouse and that a structured query contain at least one
% measure and one dimension. Other constraints 
apply on how entities occur together in the query, 
the data types of the recognized entities or 
to which other entities 
%the recognized entities 
they relate to. 
Another constraint takes the form of entity recommendation
%These includes also to suggest entities 
when the user did not include all necessary information to compute a
valid query or to add additional filter for personalization.
%
% In reality there are many and quiet complex constraints that need to be 
% ensured to compute valid structured queries. The problem that we need to 
% solve is how to encode such constraints on metadata-level without encoding 
% them into the actual program logic, which is almost impossible to manage 
% (as previous implementations of the use case
% demonstrated). In addition it make sense to separate the constraint solving
% problem from the actual mapping and query generation process to keep it managable
% and ease the configuration.
% 
% Our proposal is to express structural constraints in a SparQL {\scriptsize \verb|WHERE|} clause
%  and to select and modify properties defined in the \emph{parse graph} to be used in the technical query. 
% By defining variables in this {\scriptsize \verb|WHERE|} clause, we can separate the selection
% of items that we like to reuse in the mapping step. These variables 
%  are then mapped into the query model (representing the actual query language $L$) using
%  a {\scriptsize \verb|CONSTRUCT|} clause\footnote{\url{http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/#constructGraph}}
%  which we will detail in the next section. The main advantage of these approach is that 
%  it allows the engineer describe certain situations that may evolve from the user's question 
%  instead of programming the generation of alternative solutions.
 %
We discuss in the following two types of constraints: (1) \emph{relational
constraints} %that apply on edges and nodes in the graph 
(see section~\ref{relational-constraints})
 % They 
 which describe 
 %certain 
 situations like the fact that 
 %that we expect in the user's question 
 %(e.g. 
 a dimension and a measure 
 %that
 should belong to the same data warehouse
 %)
 and
 % the suggestion of additional artifacts that ensure the validity of the final query; 
 (2) \emph{property constraints}, which 
 %can be used to 
 filter nodes based on property
  values (see section~\ref{property-constraints}),
  like the fact that two annotations are overlapping or close to each other. 
  %to determine situations that 
  %resolve situations that
  %cannot be expressed on graph level (e.g. whether two annotations are
  % overlapping or close to each other).
 Then, we discuss a convenient feature of 
 \textsc{SparQL
 1.1}\footnote{\url{http://www.w3.org/TR/2012/WD-sparql11-query-20120724/}} to
 inject additional variables (see section~\ref{additional-variables}), e.g. to
 %define default values or 
 to generate additional values to be used in the structured query if a certain
 graph pattern occurs.

\subsection{Relational Constraints}
\label{relational-constraints}

\textsc{SparQL} queries are essentially graph patterns. 
Nodes and edges are be adressed by URIs or are assigned to 
variables
which
%if they are kind of placeholders. 
%These variables 
are bound to 
URIs or literals by the \emph{\textsc{SparQL} query processor}. 
This mechanism of expressing graph constraints and of binding variables
 eases the configuration of our approach tremendously.
%
%To demonstrate the power of our \textsc{SparQL} approach in expressing 
%complex constraints we show in 
Figure~\ref{fig:structural-constraints} 
is 
a vizualized example of complex constraints for selection and mapping rules that
are used in our application setting.
On the left-hand side 
stands an
%in figure~\ref{fig:structural-constraints} we see an
excerpt of the constraints and variables used in our BI use-case. 
%(the right
%part will be discussed in next section).
The markers attached to a node represent in contrast to
figure~\ref{fig:query-graph} assigned variables or URIs. URIs are expressed in
short form and do not care a leading question mark.
Edges between nodes and literals refer to {\footnotesize \verb|rdfs:label|} 
if there are not marked otherwise. Dashed lines illustrate that a particular
part of the graph pattern is optional (implemented trough an 
{\footnotesize \verb|OPTIONAL|} statement 
%assigned to the correpsonding block 
in \textsc{SparQL}). 
%
\circled{Q} depicts the user's question.
%The node representing the user's question is depicted on top with .
Below 
%we see 
are
 annotation nodes and left to them  
assigned variable names (like `?a1') which form the \emph{parse graph}. 
Other nodes reference metadata graphs (see figure~\ref{fig:query-graph}). 
%(we use here the same color coding). 
The 
%light colored 
nodes like \lightrednode{M} in figure~\ref{fig:structural-constraints}
represent resources, while nodes like \darkrednode{}
represent literals, which will be reused later for query composition. 
%As we will detail 
As discussed in next section, we map only literal variables to the final query
model, to separate the input and output model on conceptual level. Note also
that we define much more variables in the real-world use-case, e.g. to handover
data types and scores from the question to the query model, which we leave out
of the examples for sake of brevity. Our example exhibits constraints for the
 following situations:\\
 %
\textbf{Natural Language Patterns (`?a1'):} The annotation (`?a1') addresses 
the natural language pattern for \emph{TopK} (see figure~\ref{fig:query-graph}).
The \emph{TopK} pattern exports the variables `number' and  `order', which are 
bound to `?nb' and `?ord'. This rule might be combined with a rule triggered by phrases like
`order by \ldots' to assign a variable holding the dimension or measure 
%for 
such
that an ordering 
%shall 
can
be applied. 
%but we like to show here how we handle situations without such user input. 
In general, 
%one can easily combine 
different natural language patterns 
can be easily combined
%by 
using
\emph{property constraints} as explained in next subsection.
%
Patterns for ranges, custom vocabulary, \emph{my}-questions 
%and so on
etc. 
are treated 
%in a similar fashion
similarly. In particular 
%for
in situations related to 
ranges and the mapping of other data types, we define additional variables for
the data type of certain objects (e.g. `Date' or `Numeric') to handle
them separately in the final query generation. These attributes eventually
influence the \emph{serialization} of the structured query.\\
%, e.g. to
%encode filters on string data types with surrounding quotes.\\    
%
\textbf{Data Warehouse Metadata (`?a2' and `?a3'):} The 
%second and third 
annotations `?a2' and `?a3' refer to a recognized measure and dimension bound
via a \emph{matches} relationship in figure~\ref{fig:structural-constraints}
and triggered by questions like ``revenue per year''. 
%Note that we
 %show here only
 %the assigment of one measure and dimension, while we 
 %actually allow 
An arbitrary number of measures and two dimensions are allowed (due to the
requirement of rendering charts).
 % in the real-world use-case
By assigning the nodes for the measure (`?m1') and dimension (`?d1') to the same
node for the data warehouse (`?w') we ensure that these objects 
%are \emph{compatible}
%(i.e. 
can be used together in a structured query
%) 
and lead therefore to a valid query. 
%In reality, we further check whether
More precisely we check whether recognized dimensions and measures are linked
through a fact table (see figure~\ref{fig:data-schema}).
For reuse in the structured query, we assign the labels of the recognized objects to 
variables (i.e. `?mL1' for the measure label and `?dL1' for the dimension label).
%
%As discussed in section~\ref{sec:problem}, there might also be cases where
%the user mentions only one of the object types: either measures or dimensions,
%to get an overview of his data warehouse from multiple views. 
In 
%such 
some
cases
the system has to suggest fitting counterparts 
(e.g. \emph{compatible} dimensions)
%(e.g. \emph{compatible} 
%dimensions for a measure) 
to not aggregate all facts. 
%for the mentioned measures
% or show all values of the mentioned dimensions.
%, which would not be very usefull in a real-world BI scenario.
%
In the example in figure~\ref{fig:data-schema} we choose `?d4' as dimension if
the question contains only measures and `?m2' as measure if it contains only
dimensions. Thus the system generates multiple interpretations for the user's
question.
%by proposing different views on the warehouse's data. 
The \textsc{SparQL} blocks that contain `?d4' and `?m2' are optional and contain
a filter (i.e. a \emph{property constraint} as explained later) such that they
are only triggered if either `?mL1' or `dL1' are not bound. The label of the
recommended measure or dimension is finally bound to the respective label
variable that would otherwise be unbound (i.e. `?mL1' or `dL1').\\
 %This is again a very good example
 %on how easy it is to model different match situations with our declarative
 % Q\&A framework. 
%
\textbf{Data Warehouse Values (`?a4'):} 
%Matches for dimension values 
%are differently handled than matches on dimension names
% as shown for `?a4' in figure~\ref{fig:structural-constraints}. 
% We use 
Instead of the \emph{matches} relationship, we use the URI
\emph{valueOf} to assign the dimension value to the corresponding dimension
(i.e. `?d2'). For later reuse, we assign the label of the value's node (`?vL2'),
e.g. `2009' for a year, and the dimension value to a variable (`?dL2'). 
%In addition
%we ensure that `?d2' is compatible with the other other 
%data warehouse 
%objects. 
%used in this interpretation.
% / structured query (ensuring that there is a
%relation \emph{dimOf} starting at `?d2' and ending at `?w').
%
In the real-world use-case we consider not only one match situation (like in
the example) but a couple of other situations, where the declarative
approach is very valuable. For instance, we show here only the case where the
matched value does not belong to an already-recognized dimension (i.e. `d2'
would be an additonal dimension in the query).
For the situation where the value belongs to `?d1' -- an already-recognized
dimensions -- we define another optional \textsc{SparQL} block which is
triggered by the \emph{valueOf} relationship between the annotation and the
corresponding dimension.
%
%If there is more than one recognized value, we need to assign them to the 
%corresponding dimensions, which can be easily done with graph patterns. 
%In addition, we like to t
We treat single value matches for one dimension differently than matches on
multiple values that belong to the same dimension.
%(i.e. to define an additional
%projection finally as discussedd in section~\ref{sec:problem}). 
Our declarative approach eases this, because another set of constraints can be
simply defined with separate variables.\\ 
%that are only used in the mapping step if
%such situations occurs.\\
%
\textbf{Personalization (`?a5'):} Annotation `?a5' shows the personalization
feature, which applies a filter for a 
%mentioned 
dimension if a corresponding value is part of the user profile (see `my city'
in figure~\ref{fig:translation-process}).
The constraint captures following situation: an annotation (`?a5') refers to a 
dimension (`?d3') that \emph{occursIn} some resource (`?profileItem') that 
%in turn 
has some relationship (`?rel') to the user (`?user'). From the 
%defined
graph pattern, we consider for later porcessing the label of the 
%mentioned
dimension (`?dL3') and the label of the user profile 
%value 
that occurs in this dimension (`?pItemL').
%
Note that  constraints for personalization (as shown in 
figure~\ref{fig:structural-constraints}) do not refer to the  \emph{my}-pattern
(shown in figure~\ref{fig:query-graph}) due to space constraints. If the
constraints would be applied as shown here, we would simply test for every
matched dimension whether there is a value mapping to the user profile. 
%
%In summary, 
These examples 
%mentioned above 
highlight the flexibility 
%and convinence 
of using \textsc{SparQL} graph patterns to manage constraints and variables
%that shall be used 
for query composition in Q\&A systems.
%In particular the assigment of suggested measures and  
%dimensions for `incomplete' user questions and ease in describing 
% different match situations demonstrate the power of our approach. 
%Still, graph patterns are not enough. 
Addtitional constraints have to be applied on property or litteral level (see
the following sub-section).

\subsection{Property Constraints}
\label{property-constraints}
The following details the use of constraints through \textsc{SparQL}
{\footnotesize\verb|FILTER| statements} 
%In the following we 
%like to 
%give examples for constraints (or more specificly \textsc{SparQL}
% {\footnotesize \verb|FILTER| statements}) that have to be 
considered in addition to graph patterns. They are less important on conceptual
level, but have many practical implications, e.g. to not generate duplicated
queries or to add further functionality, which cannot be expressed on graph
pattern level.
%
The first obvious additional constraint is to check whether 
two annotations 
%that shall for instance 
matching two distinct dimensions are different:\\
%, using for instance
%\vspace{-2mm}
{\footnotesize \verb$FILTER(!sameTerm(?a1, ?a2))$}\\
%
We mentioned in section~\ref{sec:problem} that  
it is often crucial to separate objects  
that matched the same part of the user's question into 
several structured query;
%(e.g. if the user entered `New York',
%one match is derived on a value for the dimension `state' and 
%another one for the dimension `city').
this is even more important for dimension names because they 
define the aggregation level of the final result. 
%
This kind of constraints can be expressed using the metadata 
acquired during the matching process. Assuming that the 
%offset of one annotation (i.e. the 
position of a match inside the question has been assigned to the variable
{\footnotesize \verb$?o1$} and the offset and length of another annotation are
assigned to {\footnotesize \verb$?o2$} and {\footnotesize \verb$?l2$},
the filter for ensuring that the latter one does not begin within
the range of the first annotation can be expressed by:\\
{\footnotesize \verb$FILTER(?o2 < ?o1 || ?o2 > (?o1 + ?l2)))$}\\
Property constraints are also used for 
%a number of 
more complicated
query generation problems. 
%A nice example are range queries for 
%arbitrary numeric dimension values. One
%can 
For instance a generic \emph{natural language pattern} for ranges would
look similar as the one shown in figure~\ref{rule_example}. It would then apply
to {\footnotesize\verb?dataType:Numeric?}, be triggered by phrases like `between
$x$ and $y$' and include a script for normalizing numbers. In combination
with matched numeric dimension values, one can define a filter that tests
whether two members where matched inside the matched range phrase and generate
variables defining the beginning and ending of a structured range query.

\subsection{Additional Variables}
\label{additional-variables}

It is often usefull to define default values or to bind additional
variables.
%for other purposes based on some constraints, 
%which is possible by using \emph{SparQL 1.1}.
% 
An example for a default value would be to limit the size of the 
query results if it is not specified by the user. To do so, we add 
an optional \textsc{SparQL} block that checks the variable `?nb' 
and assigns a value if it is unbound using: 
% The following 
% statement inside an optional \textsc{SparQL} block that 
% checks whether the variable `?nb' was already bound beforehand:\\
{\footnotesize \verb$BIND(1000 AS ?nb)$}.\\
%\\{\footnotesize \verb$BIND('ASC' AS ?ord)$}
%
There are plenty of other use-cases to inject additional variables,
%For instance one can 
like defining analysis types (which are part of the 
not-illustrated metadata that is assigned to a structured query). 
These are indicators used to select the best fitting chart type for 
a single result. To capture the analysis type, we use 
certain trigger-words (see \cite{text2query}) and additional 
constraints such as the number of measures and dimensions and the 
 cardinality of dimensions. For instance we would select a \emph{pie chart}
 if a single measure and dimensions is mentioned in the question 
 and the user is interested in a `comparison' 
 (e.g. triggered by  the term `compare' or `versus'). However, if the cardinality
 of the dimension (which is maintained in the metadata graph) would exceed 
 a certain value (e.g. 10), a \emph{bar chart} would be a better fit because a
 pie chart would be difficult to interpret otherwise.




 

 
 